import java.util.ArrayList;
import java.util.List;

/**
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 * <p>
 * 示例:
 * <p>
 * 输入: n = 4, k = 2
 * 输出:
 * [
 * [2,4],
 * [3,4],
 * [2,3],
 * [1,2],
 * [1,3],
 * [1,4],
 * ]
 */
class Solution {

    public static void main(String[] args) {
        // System.out.println(combine(4, 2).size());
        System.out.println(combine(1, 1).size());
    }

    /**
     * 其实就是选C(N,M)
     *
     * @param n
     * @param k
     * @return
     */
    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> all = new ArrayList<List<Integer>>();
        if (k > n) {
            return all;
        } else if (k == n) {
            List<Integer> list = new ArrayList<>();
            for (int j = 1; j <= n; j++) {
                list.add(j);
            }
            all.add(list);
        } else {
            List<Integer> list = new ArrayList<>();
            list.add(1);
            combine(all, list, 2, n, k);
            combine(all, new ArrayList<>(), 2, n, k);
        }
        return all;
    }

    /**
     * 递归
     *
     * @param all
     * @param list
     * @param i
     * @param n
     * @param k
     */
    private static void combine(List<List<Integer>> all, List<Integer> list, int i, int n, int k) {
        // 如果已经满了
        if (list.size() == k) {
            all.add(list);
            return;
        }
        int count = list.size() + n - i + 1;
        if (count > k) {
            // 在列表中加入了i的情况
            List<Integer> newList = new ArrayList<>(list);
            newList.add(i);
            combine(all, newList, i + 1, n, k);
            // 在列表中没加入了i的情况
            combine(all, list, i + 1, n, k);
        } else if (count == k) {
            for (int j = i; j <= n; j++) {
                list.add(j);
            }
            all.add(list);
        }
    }
}